package org.basis.algorithm.practice;

import lombok.Data;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

/**
 * 最近公共祖先
 *
 * @author Mr_wenpan@163.com 2022/03/21 20:09
 */
public class LowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode head = new TreeNode("1");
        head.left = new TreeNode("2");
        head.right = new TreeNode("3");
        head.left.left = new TreeNode("4");
        head.left.right = new TreeNode("5");
        head.right.left = new TreeNode("6");
        head.right.right = new TreeNode("7");
        head.right.right.left = new TreeNode("8");

        TreeNode o1 = head.left.right;
        TreeNode o2 = head.right.left;

        System.out.println("o1 : " + o1.val);
        System.out.println("o2 : " + o2.val);
        System.out.println("ancestor : " + findLowestCommonAncestor(o1, o2, head).val);
        System.out.println("===============");
    }

    /**
     * 给你两个节点node1,node2，这两个节点都在树上，再给你一个节点head，head表示二叉树的头节点，请返回他们最近的公共祖先
     */
    public static TreeNode findLowestCommonAncestor(TreeNode node1, TreeNode node2, TreeNode head) {
        // 非法数据，没有公共祖先
        if (node1 == null || node2 == null || head == null) {
            return null;
        }
        if (node1 == node2) {
            return node1;
        }
        // 先将父子关系保存到map中
        HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
        // 用先序遍历的方式保存各个节点的父子关系
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            // 先压右再压左
            if (pop.right != null) {
                parentMap.put(pop.right, pop);
                stack.push(pop.right);
            }
            if (pop.left != null) {
                parentMap.put(pop.left, pop);
                stack.push(pop.left);
            }
        }

        HashSet<TreeNode> set = new HashSet<>();
        // 从node1节点开始，一直向上找他的父节点，并保存到set中
        TreeNode cur = node1;
        while (cur != null) {
            set.add(cur);
            cur = parentMap.get(cur);
        }

        // 从node1节点开始，依次找他的父节点
        cur = node2;
        while (cur != null) {
            // 第一个contains的节点就是他们最近的公共祖先，类似于单链表相交问题
            if (set.contains(cur)) {
                return cur;
            }
            cur = parentMap.get(cur);
        }

        // 没有公共祖先
        return null;
    }
}

@Data
class TreeNode {
    String val;
    TreeNode left;
    TreeNode right;

    public TreeNode(String val) {
        this.val = val;
    }
}
